<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>第 1 节 分而治之的算法设计思想 | 算法不好玩</title>
    <meta name="generator" content="VuePress 1.8.2">
    <link rel="icon" href="/book/logo.png">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.10.0/github-markdown.min.css">
    <meta name="description" content="">
    
    <link rel="preload" href="/book/assets/css/0.styles.e159a327.css" as="style"><link rel="preload" href="/book/assets/js/app.a4355b0d.js" as="script"><link rel="preload" href="/book/assets/js/2.ba785ee6.js" as="script"><link rel="preload" href="/book/assets/js/27.b6eae7df.js" as="script"><link rel="prefetch" href="/book/assets/js/10.b6950be1.js"><link rel="prefetch" href="/book/assets/js/11.f4ee7d6e.js"><link rel="prefetch" href="/book/assets/js/12.50fe1ace.js"><link rel="prefetch" href="/book/assets/js/13.42356fcc.js"><link rel="prefetch" href="/book/assets/js/14.e740c742.js"><link rel="prefetch" href="/book/assets/js/15.05c628f7.js"><link rel="prefetch" href="/book/assets/js/16.bd9bc9d5.js"><link rel="prefetch" href="/book/assets/js/17.e120b4fc.js"><link rel="prefetch" href="/book/assets/js/18.398213f8.js"><link rel="prefetch" href="/book/assets/js/19.e29ad0b2.js"><link rel="prefetch" href="/book/assets/js/20.14e30c1c.js"><link rel="prefetch" href="/book/assets/js/21.4f05f6c9.js"><link rel="prefetch" href="/book/assets/js/22.98fbf199.js"><link rel="prefetch" href="/book/assets/js/23.285387f4.js"><link rel="prefetch" href="/book/assets/js/24.852addbe.js"><link rel="prefetch" href="/book/assets/js/25.d30ade13.js"><link rel="prefetch" href="/book/assets/js/26.23dfa040.js"><link rel="prefetch" href="/book/assets/js/28.97878b08.js"><link rel="prefetch" href="/book/assets/js/29.7217a3d0.js"><link rel="prefetch" href="/book/assets/js/3.f0c15194.js"><link rel="prefetch" href="/book/assets/js/30.0ced5a5a.js"><link rel="prefetch" href="/book/assets/js/31.8f432033.js"><link rel="prefetch" href="/book/assets/js/32.aac9aa62.js"><link rel="prefetch" href="/book/assets/js/33.db835477.js"><link rel="prefetch" href="/book/assets/js/34.a1a59c2a.js"><link rel="prefetch" href="/book/assets/js/35.ed2ef96b.js"><link rel="prefetch" href="/book/assets/js/36.48099c55.js"><link rel="prefetch" href="/book/assets/js/37.32827612.js"><link rel="prefetch" href="/book/assets/js/38.58abec0e.js"><link rel="prefetch" href="/book/assets/js/39.f6eb3874.js"><link rel="prefetch" href="/book/assets/js/4.13ea3b32.js"><link rel="prefetch" href="/book/assets/js/40.80523ed8.js"><link rel="prefetch" href="/book/assets/js/41.f7b72b7a.js"><link rel="prefetch" href="/book/assets/js/42.44e40de9.js"><link rel="prefetch" href="/book/assets/js/43.065f077f.js"><link rel="prefetch" href="/book/assets/js/44.386d9aea.js"><link rel="prefetch" href="/book/assets/js/45.d8a88f16.js"><link rel="prefetch" href="/book/assets/js/46.33bc2083.js"><link rel="prefetch" href="/book/assets/js/47.e7767237.js"><link rel="prefetch" href="/book/assets/js/48.9bb76138.js"><link rel="prefetch" href="/book/assets/js/49.c2ca5c29.js"><link rel="prefetch" href="/book/assets/js/5.32eda204.js"><link rel="prefetch" href="/book/assets/js/50.1242fe24.js"><link rel="prefetch" href="/book/assets/js/51.e8f8117d.js"><link rel="prefetch" href="/book/assets/js/52.eae5648f.js"><link rel="prefetch" href="/book/assets/js/53.39876d83.js"><link rel="prefetch" href="/book/assets/js/6.1c662163.js"><link rel="prefetch" href="/book/assets/js/7.29470445.js"><link rel="prefetch" href="/book/assets/js/8.814b737f.js"><link rel="prefetch" href="/book/assets/js/9.d4211262.js">
    <link rel="stylesheet" href="/book/assets/css/0.styles.e159a327.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container no-sidebar"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/book/" class="home-link router-link-active"><!----> <span class="site-name">算法不好玩</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link router-link-active">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/book/" class="nav-link">
  主页
</a></div><div class="nav-item"><a href="/book/guide/" class="nav-link">
  关于我
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="基础算法与数据结构" class="dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow down"></span></button> <button type="button" aria-label="基础算法与数据结构" class="mobile-dropdown-title"><span class="title">基础算法与数据结构</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          排序算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 1 章 二分查找
</a></li><li class="dropdown-subitem"><a href="/book/algs/recursion/" class="nav-link router-link-active">
  第 2 章 递归
</a></li></ul></li><li class="dropdown-item"><h4>
          数组里的算法
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/book/algs/01-binary-search/" class="nav-link">
  第 4 章 滑动窗口
</a></li><li class="dropdown-subitem"><a href="/book/algs/02-basic-sorting/" class="nav-link">
  第 5 章 双指针
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="威威道来" class="dropdown-title"><span class="title">威威道来</span> <span class="arrow down"></span></button> <button type="button" aria-label="威威道来" class="mobile-dropdown-title"><span class="title">威威道来</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/book/talk-show/2021-04/" class="nav-link">
  2021 年 4 月
</a></li></ul></div></div><div class="nav-item"><a href="https://leetcode-cn.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  力扣
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://gitee.com/liweiwei1419/book/pages" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Gitee 部署页面
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav>  <!----> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="第-1-节-分而治之的算法设计思想"><a href="#第-1-节-分而治之的算法设计思想" class="header-anchor">#</a> 第 1 节 分而治之的算法设计思想</h1> <h2 id="递归与分治"><a href="#递归与分治" class="header-anchor">#</a> 递归与分治</h2> <ul><li>递归是编程技巧，<strong>直接体现在代码上</strong> ，即 <strong>函数自己调用自己</strong>，每一层递归调用，传入的参数的值并不完全一样；</li> <li>分治是一种算法设计的思想，绝大部分情况下「分治算法」通过「递归」实现。即：子问题的求解通过递归方法实现。</li></ul> <p>算法和数据结构并不是凭空想象出来的，「递归」函数也不例外。「递归」函数基于 <strong>「自顶向下」拆分问题，再「自底向上」逐层解决问题的思想</strong> 设计而成，这是所熟知的「分而治之」的算法思想。</p> <h2 id="递归函数的设计思想-分而治之-减而治之"><a href="#递归函数的设计思想-分而治之-减而治之" class="header-anchor">#</a> 递归函数的设计思想：分而治之（减而治之）</h2> <p>分而治之（Divide-and-Conquer）的思想分为如下三步：</p> <ol><li><strong>拆分</strong>：将原问题拆分成若干个子问题；</li> <li><strong>解决</strong>：解决这些子问题；</li> <li><strong>合并</strong>：合并子问题的解得到原问题的解。</li></ol> <p><strong>注意</strong>：第 2 步「解决这些子问题」不是逐个解决。是以一种「深度优先」或者说「递归」的方式解决某个子问题，等到该子问题解决完成以后，在解决同一层的其它子问题。大家可以结合我们后面给出的例子进行理解。</p> <p>典型的分治思想的应用是：归并排序、快速排序、绝大多数「树」中的问题（先把原问题拆分成子树的问题，当子树中的问题解决以后，结合子树求解的结果处理当前结点）、链表中的问题。</p> <p>我们在本教程里不对「分治思想」展开叙述。</p> <p>「分治思想」的特例是「减治思想（Decrease-and-Conquer）」：每一步将问题转换成为规模更小的子问题。「减治思想」思想的典型应用是「二分查找」「选择排序」「插入排序」「快速排序」算法。「分治」与「减治思想」的区别如下：</p> <ul><li>分治思想：将一个问题拆分成若干个子问题，然后再逐个求解，根据各个子问题得到的结果得到原问题的结果；</li> <li>减治思想：在拆分子问题的时候，只将原问题转化成 <strong>一个</strong> 规模更小的子问题，因此子问题的结果就是上一层原问题的结果，每一步只需要解决一个规模更小的子问题，相比较于「分治思想」而言，它 <strong>没有「合并」的过程</strong>。</li></ul> <hr> <h2 id="自顶向下地解决问题"><a href="#自顶向下地解决问题" class="header-anchor">#</a> 自顶向下地解决问题</h2> <p>使用「递归」的思想解决问题的方案是：从「结果」推向「源头」，再从「源头」返回「结果」。我们以计算 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mn class="mjx-n"><mjx-c c="5"></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c="!"></mjx-c></mjx-mo></mjx-math></mjx-container> 为例向大家解释什么是「自顶向下」地解决问题。</p> <p>下面的幻灯片演示了使用「递归」方法「自顶向下」地计算 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mn class="mjx-n"><mjx-c c="5"></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c="!"></mjx-c></mjx-mo></mjx-math></mjx-container> 的步骤。编程语言在执行计算的过程中，使用了数据结构「栈」。</p> <p>&lt;<img src="https://pic.leetcode-cn.com/1616382148-PLiIto-recursion.001.jpeg" alt="recursion.001.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-pxxYsj-recursion.002.jpeg" alt="recursion.002.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-wRLHqR-recursion.003.jpeg" alt="recursion.003.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-qLQgWz-recursion.004.jpeg" alt="recursion.004.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-zkKIUh-recursion.005.jpeg" alt="recursion.005.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-qbqYUq-recursion.006.jpeg" alt="recursion.006.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-wrCbIX-recursion.007.jpeg" alt="recursion.007.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-ZEoXtQ-recursion.008.jpeg" alt="recursion.008.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-KLUAzN-recursion.009.jpeg" alt="recursion.009.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-BSTCQZ-recursion.010.jpeg" alt="recursion.010.jpeg">,<img src="https://pic.leetcode-cn.com/1616382148-mmqxwT-recursion.011.jpeg" alt="recursion.011.jpeg">&gt;</p> <hr> <h2 id="为什么需要使用栈"><a href="#为什么需要使用栈" class="header-anchor">#</a> 为什么需要使用栈？</h2> <p>在计算 <mjx-container jax="CHTML" class="MathJax"><mjx-math class=" MJX-TEX"><mjx-mn class="mjx-n"><mjx-c c="5"></mjx-c></mjx-mn><mjx-mo class="mjx-n"><mjx-c c="!"></mjx-c></mjx-mo></mjx-math></mjx-container> 的过程当中，需要记录拆分的过程当中的每一个子问题，并且在求解每一个子问题以后，逐层向上汇报结果。<strong>后拆分的子问题先得到了解决，整个过程恰好符合「后进先出」的规律</strong> ，因此需要借助的数据结构是「栈」。</p> <h2 id="拆分的时候「先走出去」-合并的时候「再走回来」"><a href="#拆分的时候「先走出去」-合并的时候「再走回来」" class="header-anchor">#</a> 拆分的时候「先走出去」，合并的时候「再走回来」</h2> <p>使用「递归」实现的算法需要走完下面两条路径：</p> <ul><li>先「自顶向下」拆分问题，直到不能拆分为止；</li> <li>再「自底向上」逐层把底层的结果向上汇报，直至得到原问题的解。</li></ul> <p>因此使用「递归」函数解决的问题如上图所示，有「<strong>先走出去，再走回来</strong>」的过程。</p> <h2 id="总结"><a href="#总结" class="header-anchor">#</a> 总结</h2> <ul><li>「分治」是思想，「减治」是分治的特例；</li> <li>「递归」是代码表现形式；</li> <li>「递归」有先拆分问题的过程，真正解决问题，需要在拆分到底以后，一层一层向上返回。</li></ul></div> <footer class="page-edit"><!----> <!----></footer> <!----> </main></div><div class="global-ui"><!----></div></div>
    <script src="/book/assets/js/app.a4355b0d.js" defer></script><script src="/book/assets/js/2.ba785ee6.js" defer></script><script src="/book/assets/js/27.b6eae7df.js" defer></script>
  </body>
</html>
